package simple;

import data.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/3/22 20:12
 */
public class No21_合并两个有序链表 {
    public static void main(String[] args) {
        Solution21 solution21 = new Solution21();
        ListNode l1 = new ListNode(2);
        l1.add(3);
        l1.add(7);
        l1.add(9);
        ListNode l2 = new ListNode(1);
        l2.add(5);
        l2.add(8);

        ListNode result = solution21.mergeTwoLists(l1, l2);
        System.out.println();

    }
}

class Solution21 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //超级烧脑,3指针游荡
        ListNode red = l1;
        ListNode green = l2;
        ListNode yellow = new ListNode(-1);
        yellow.next = red;
        ListNode yellowCp = yellow;
        boolean flag = true; //表示red小于等于green
        while (red != null && green != null) {
            if (red.val <= green.val) {
                if (flag) {
                    //红2号
                    red = red.next;
                    yellow = yellow.next;
                } else {
                    //红3号
                    yellow.next = red;
                    red = red.next;
                    yellow = yellow.next;
                    flag = true;
                }
            } else {
                if (flag) {
                    //绿3号
                    yellow.next = green;
                    green = green.next;
                    yellow = yellow.next;
                    flag = false;
                } else {
                    //绿2号
                    green = green.next;
                    yellow = yellow.next;
                }
            }
        }
        if (red == null) {
            yellow.next = green;
        } else if (green == null) {
            yellow.next = red;
        }
        return yellowCp.next;
    }

}

    //public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //    //递归,这时候要考虑list原本需要排序状态
    //    if (l1 == null) {
    //        return l2;
    //    } else if (l2 == null) {
    //        return l1;
    //    } else if (l1.val > l2.val) {
    //        l2.next = mergeTwoLists(l1, l2.next);
    //        return l2;
    //    } else if (l1.val <= l2.val) {
    //        l1.next = mergeTwoLists(l1.next, l2);
    //        return l1;
    //    } else {
    //        return null;
    //    }
    //
    //}

    //public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //    ListNode result = new ListNode(-1);
    //    //双指针,找寻插入位置
    //    while (l1 != null) {
    //        int data = l1.val;
    //        addSortList(result, data);
    //        l1 = l1.next;
    //    }
    //    while (l2 != null) {
    //        int data = l2.val;
    //        addSortList(result, data);
    //        l2 = l2.next;
    //    }
    //    return result.next;
    //}
    //
    ////每次进来,sortListHead都会称为一个新的排序链表
    //public void addSortList(ListNode sortListHead, int compareData) {
    //    //元素
    //    ListNode input = new ListNode(compareData);
    //    ListNode red = sortListHead;
    //    ListNode green = sortListHead.next;
    //    if (sortListHead.next == null) {
    //        sortListHead.next = input;
    //        return;
    //    }
    //    //头插
    //    if (green.val > compareData) {
    //        input.next = green;
    //        red.next = input;
    //        return;
    //    }
    //
    //    //其他情况
    //    while (green != null && green.val < compareData) {
    //        red = red.next;
    //        green = green.next;
    //    }
    //    input.next = green;
    //    red.next = input;
    //}

    //public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //    //鸡贼法,十分鸡贼
    //    List<Integer> list = new ArrayList<>();
    //    //头
    //    ListNode result = new ListNode(-1);
    //    //遍历l1
    //    while (l1 != null) {
    //        int data = l1.val;
    //        list.add(data);
    //        l1 = l1.next;
    //    }
    //    //遍历l2
    //    while (l2 != null) {
    //        int data = l2.val;
    //        list.add(data);
    //        l2 = l2.next;
    //    }
    //    //这时候,list已经加完
    //    //list排序
    //    list.sort(new Comparator<Integer>() {
    //        @Override
    //        public int compare(Integer o1, Integer o2) {
    //            return o1 >= o2 ? 1 : -1; // 从小到大
    //        }
    //    });
    //    //遍历list,元素添加
    //    for (int i : list) {
    //        //链表元素添加
    //        addList(result, i);
    //    }
    //    return result.next;
    //}
    //
    //public void addList(ListNode head, int data) {
    //    //保存
    //    ListNode headCp = head;
    //    while (head != null && head.next != null) {
    //        head = head.next;
    //    }
    //    head.next = new ListNode(data);
    //    head = headCp;
    //}